//===--- DependencyGraph.h - Track intra-module dependencies ----*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// This source file is part of the polarphp.org open source project
//
// Copyright (c) 2017 - 2019 polarphp software foundation
// Copyright (c) 2017 - 2019 zzu_softboy <zzu_softboy@163.com>
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://polarphp.org/LICENSE.txt for license information
// See https://polarphp.org/CONTRIBUTORS.txt for the list of polarphp project authors
//
// Created by polarboy on 2019/11/26.

#ifndef POLARPHP_DRIVER_DEPENDENCYGRAPH_H
#define POLARPHP_DRIVER_DEPENDENCYGRAPH_H

#include "polarphp/ast/DiagnosticEngine.h"
#include "polarphp/basic/LLVM.h"
#include "polarphp/basic/OptionSet.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/PointerLikeTypeTraits.h"
#include <string>
#include <vector>

namespace llvm {
class MemoryBuffer;
}

namespace polar {
class UnifiedStatsReporter;
}

namespace polar::driver {

using polar::OptionSet;
using polar::UnifiedStatsReporter;
using polar::DiagnosticEngine;

/// The non-templated implementation of DependencyGraph.
///
/// \see DependencyGraph
class DependencyGraphImpl
{
public:
   /// Possible dependency kinds.
   ///
   /// Clients of DependencyGraph should have no reason to use this type.
   /// It is only used in the implementation.
   enum class DependencyKind : uint8_t;

   /// Describes the result of loading a dependency file for a particular node.
   enum class LoadResult
   {
      /// There was an error loading the file; the entire graph should be
      /// considered suspect.
      HadError,

      /// The file was loaded successfully; with current information the node
      /// does not need to be rebuilt.
      UpToDate,

      /// The file was loaded successfully; anything that depends on the node
      /// should be considered out of date.
      AffectsDownstream
   };

   /// The non-templated implementation of DependencyGraph::MarkTracer.
   ///
   /// \see DependencyGraph::MarkTracer
   class MarkTracerImpl
   {
   private:
      class Entry;
      llvm::DenseMap<const void *, SmallVector<Entry, 4>> m_table;
      UnifiedStatsReporter *m_stats;

      friend class DependencyGraphImpl;
   protected:
      explicit MarkTracerImpl(UnifiedStatsReporter *stats);
      ~MarkTracerImpl();
      void countStatsForNodeMarking(const OptionSet<DependencyKind> &kind,
                                    bool cascading) const;
      void printPath(raw_ostream &out, const void *item,
                     llvm::function_ref<void(const void *)> printItem) const;
   };

private:
   enum class DependencyFlags : uint8_t;
   using DependencyMaskTy = OptionSet<DependencyKind>;
   using DependencyFlagsTy = OptionSet<DependencyFlags>;

   struct DependencyEntryTy
   {
      const void *node;
      DependencyMaskTy kindMask;
      DependencyFlagsTy flags;
   };
   static_assert(std::is_move_constructible<DependencyEntryTy>::value, "");

   struct ProvidesEntryTy
   {
      std::string name;
      DependencyMaskTy kindMask;
   };
   static_assert(std::is_move_constructible<ProvidesEntryTy>::value, "");

   /// The "outgoing" edge map. This lists all outgoing (kind, string) edges
   /// representing satisfied dependencies from a particular node.
   ///
   /// For multiple outgoing edges with the same string, the kinds are combined
   /// into one field.
   ///
   /// \sa DependencyMaskTy
   llvm::DenseMap<const void *, std::vector<ProvidesEntryTy>> m_provides;

   /// The "incoming" edge map. Semantically this maps incoming (kind, string)
   /// edges representing dependencies to the nodes that depend on them, as
   /// well as a flag marking whether that (kind, string) pair has been marked
   /// dirty.
   ///
   /// The representation is a map from strings to kind mask / node pairs, plus
   /// a mask of kinds that have been marked dirty. This is because it is
   /// unusual (though not impossible) for dependencies of different kinds to
   /// have the same strings. In the case of multiple incoming edges with the
   /// same string, the kinds are combined into the one field.
   ///
   /// \sa DependencyMaskTy
   llvm::StringMap<std::pair<std::vector<DependencyEntryTy>, DependencyMaskTy>> m_dependencies;

   /// The set of marked nodes.
   llvm::SmallPtrSet<const void *, 16> m_marked;

   /// A list of all external dependencies that cannot be resolved from just this
   /// dependency graph. Each member of the set is the name of a file which is
   /// not in the module. These files' contents may (or may not) have affected
   /// the module's compilation. This list may even include the paths of
   /// non-existent files whose absence is significant.
   ///
   /// Furthermore, this set might not exhaustive. It only includes dependencies
   /// that will be checked by the driver's incremental mode.
   /// For example, it might excludes headers in the SDK if the cost
   /// of `stat`ing them were to outweigh the likelihood that they would change.
   llvm::StringSet<> m_externalDependencies;

   /// The interface hash for each node. This determines if the interface of
   /// a modified file has changed.
   ///
   /// \sa SourceFile::getInterfaceHash
   llvm::DenseMap<const void *, std::string> m_interfaceHashes;

   LoadResult loadFromBuffer(const void *node, llvm::MemoryBuffer &buffer);

protected:
   LoadResult loadFromString(const void *node, StringRef data);
   LoadResult loadFromPath(const void *node, StringRef path);

   void addIndependentNode(const void *node)
   {
      bool newlyInserted = m_provides.insert({node, {}}).second;
      assert(newlyInserted && "node is already in graph");
      (void)newlyInserted;
   }

   /// See DependencyGraph::markTransitive.

   void markTransitive(SmallVectorImpl<const void *> &visited,
                       const void *node, MarkTracerImpl *tracer = nullptr);

   bool markIntransitive(const void *node)
   {
      assert(m_provides.count(node) && "node is not in the graph");
      return m_marked.insert(node).second;
   }

   void markExternal(SmallVectorImpl<const void *> &visited,
                     StringRef externalDependency);

   bool isMarked(const void *node) const
   {
      assert(m_provides.count(node) && "node is not in the graph");
      return m_marked.count(node);
   }

public:
   decltype(m_externalDependencies.keys()) getExternalDependencies() const
   {
      return m_externalDependencies.keys();
   }
};

/// Tracks dependencies between opaque nodes.
///
/// This is implemented in terms of separate "depends" and "provides" sets
/// that together represent edges between nodes. Abstractly, each edge is
/// labeled with a (kind, string) pair, where the "kind" distinguishes
/// different kinds of dependencies. A node's "provides" set is matched up
/// with other nodes' "depends" sets to form a traversable directed graph.
/// Information on a particular node can be updated at any time, which will
/// affect any following operations. The "depends" entries can be "cascading"
/// or "non-cascading", which describes whether or not downstream nodes should
/// be traversed after following a particular dependency edge.
///
/// The graph also supports a "mark" operation, which is intended to track
/// nodes that have been not just visited but transitively marked through.
template <typename T>
class DependencyGraph : public DependencyGraphImpl
{
   using Traits = llvm::PointerLikeTypeTraits<T>;
   static_assert(Traits::NumLowBitsAvailable >= 0, "not a pointer-like type");

   static void copyBack(SmallVectorImpl<T> &result,
                        ArrayRef<const void *> rawNodes)
   {
      result.reserve(result.size() + rawNodes.size());
      std::transform(rawNodes.begin(), rawNodes.end(), std::back_inserter(result),
                     [](const void *rawNode) {
         return Traits::getFromVoidPointer(const_cast<void *>(rawNode));
      });
   }

public:
   /// Traces the graph traversal performed in DependencyGraph::markTransitive.
   ///
   /// This is intended to be a debugging aid.
   class MarkTracer : public MarkTracerImpl
   {
   public:
      explicit MarkTracer(UnifiedStatsReporter *Stats)
         : MarkTracerImpl(Stats) {}

      /// Dump the path that led to \p node.
      void printPath(raw_ostream &out, T node,
                     llvm::function_ref<void(raw_ostream &, T)> printItem) const
      {
         MarkTracerImpl::printPath(out, Traits::getAsVoidPointer(node),
                                   [printItem, &out](const void *n) {
            printItem(out, Traits::getFromVoidPointer(n));
         });
      }
   };

   /// Load "depends" and "provides" data for \p node from the file at the given
   /// path.
   ///
   /// If \p node is already in the graph, outgoing edges ("provides") are
   /// cleared and replaced with the newly loaded data. Incoming edges
   /// ("depends") are not cleared; new dependencies are considered additive.
   ///
   /// If \p node has already been marked, only its outgoing edges are updated.
   /// The third argument is ignored here, but must be present so that the same
   /// call site can polymorphically call \ref
   /// experimental_dependencies::ModuleDepGraph::loadFromPath
   LoadResult loadFromPath(T node, StringRef path, DiagnosticEngine &)
   {
      return DependencyGraphImpl::loadFromPath(Traits::getAsVoidPointer(node),
                                               path);
   }

   /// Load "depends" and "provides" data for \p node from a plain string.
   ///
   /// This is only intended for testing purposes.
   ///
   /// \sa loadFromPath
   LoadResult loadFromString(T node, StringRef data)
   {
      return DependencyGraphImpl::loadFromString(Traits::getAsVoidPointer(node),
                                                 data);
   }

   /// Adds \p node to the dependency graph without any connections.
   ///
   /// This can be used for new nodes that may be updated later.
   void addIndependentNode(T node)
   {
      return DependencyGraphImpl::addIndependentNode(Traits::getAsVoidPointer(node));
   }

   /// Marks \p node and all nodes that depend on \p node, and places any nodes
   /// that get transitively marked into \p visited.
   ///
   /// Nodes that have been previously marked are not included in \p visited,
   /// nor are their successors traversed, <em>even if their "provides" set has
   /// been updated since it was marked.</em> (However, nodes that depend on the
   /// given \p node are always traversed.)
   ///
   /// Nodes that are only reachable through "non-cascading" edges are added to
   /// the \p visited set, but are \em not added to the graph's marked set.
   ///
   /// If you want to see how each node gets added to \p visited, pass a local
   /// MarkTracer instance to \p tracer.
   ///
   /// Conservatively assumes that there exists a "cascading" edge into the
   /// starting node. Therefore, mark the start. For each visited node, add it to
   /// \p visited, and mark it if some incoming edge cascades. The start node is
   /// NOT added to \p visited.
   ///
   /// The traversal routines use
   /// \p visited to avoid endless recursion.
   template <unsigned N>
   void markTransitive(SmallVector<T, N> &visited, T node,
                       MarkTracer *tracer = nullptr)
   {
      SmallVector<const void *, N> rawMarked;
      DependencyGraphImpl::markTransitive(rawMarked,
                                          Traits::getAsVoidPointer(node),
                                          tracer);
      // FIXME: How can we avoid this copy?
      copyBack(visited, rawMarked);
   }

   template <unsigned N>
   void markExternal(SmallVector<T, N> &visited, StringRef externalDependency)
   {
      SmallVector<const void *, N> rawMarked;
      DependencyGraphImpl::markExternal(rawMarked, externalDependency);
      // FIXME: How can we avoid this copy?
      copyBack(visited, rawMarked);
   }

   /// Marks \p node without marking any dependencies.
   ///
   /// \returns true if the node is newly marked, false if not.
   ///
   /// \sa #markTransitive
   bool markIntransitive(T node)
   {
      return  DependencyGraphImpl::markIntransitive(Traits::getAsVoidPointer(node));
   }

   /// Returns true if \p node has been marked (directly or transitively).
   bool isMarked(T node) const
   {
      return DependencyGraphImpl::isMarked(Traits::getAsVoidPointer(node));
   }
};


} // polar::driver

#endif // POLARPHP_DRIVER_DEPENDENCYGRAPH_H
